#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include "Sort.h"

int main()
{
  clock_t start, finish;
  double duration;
  std::vector<int> a;
  double Tcount = 0, count = 0;
  double Order,before=0,after=0;
  double swap;
  int i,j;
  int p = 0, q = 0;
  /*for(i=0; i<50000; i++)
    a.push_back(rand());
  for( i = 0; i < a.size(); ++i )
    for( j = i+1; j < a.size(); ++j )
      {
	Tcount++;
	if( a[i] < a[j] )
	  count++;
      }
  Order = count/Tcount;
  for(p=0;p<a.size();p++)
    {
      for(q=p+1;q<a.size();q++)
	{
	  before=0;after=0;
	  if(a[p]>a[q])
	    {
	      for(i=p;i<=q;i++)
		{
		  if(a[i]>a[p]) before++;
		  if(a[i]>a[q]) after++;
		}
	      swap=a[p];a[p]=a[q];a[q]=swap;
	    }
	  count=count-before+after;
	  Order=count/Tcount;
	  if(Order>0.99) break;
	}
      if(Order>0.99) break;
    }
    Tcount = 0; count = 0;
  for( int i = 0; i < a.size(); ++i )
    for( int j = i+1; j < a.size(); ++j )
      {
	Tcount++;
	if( a[i] < a[j] )
	  count++;
      }
  Order = count/Tcount;
  std::cout << Order << std::endl;*/
  start = clock();
  heapsort( a );
  finish = clock();
  duration = (double)(finish - start) / CLOCKS_PER_SEC;
  std::cout << duration << std::endl;
  start = clock();
  quicksort( a );
  finish = clock();
  duration = (double)(finish - start) / CLOCKS_PER_SEC;
  std::cout << duration << std::endl;
  
  return 0;
}

